#define _CRT_SECURE_NO_WARNINGS 1
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* Bighead, * Bigtail;
        Bighead = Bigtail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* Smallhead, * Smalltail;
        Smallhead = Smalltail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* pcur = pHead;
        while (pcur) {
            if (pcur->val >= x) {
                Bigtail->next = pcur;
                Bigtail = Bigtail->next;
            }
            else {
                Smalltail->next = pcur;
                Smalltail = Smalltail->next;
            }
            pcur = pcur->next;
        }
        Bigtail->next = NULL;
        Smalltail->next = Bighead->next;
        ListNode* ret = Smallhead->next;
        free(Smallhead);
        free(Bighead);
        return ret;
    }
};